package 归并排序算法;

/**
 * @Classname reversePairs51
 * @Description TODO
 * @Date 2022/2/15 20:57
 * @Created by xjl
 */
public class reversePairs51 {

    int count = 0;

    public int reversePairs(int[] array) {
        // 长度小于2则无逆序对
        if (array.length < 2) {
            return 0;
        }
        // 进入归并
        mergeSort(array, 0, array.length - 1);
        return count;
    }

    private void mergeSort(int[] array, int left, int right) {
        // 找分割点
        int mid = (left + right) >> 1;
        if (left < right) {
            // 左子数组
            mergeSort(array, left, mid);
            // 右子数组
            mergeSort(array, mid + 1, right);
            // 合并数组
            merge(array, left, mid, right);
        }
    }

    private void merge(int[] array, int left, int mid, int right) {
        // 创建临时数组，长度为此时两个子数组加起来的长度
        int[] arr = new int[right - left + 1];
        // 临时数组的下标起点
        int index = 0;

        // 保存在原数组的起点下标值
        int s = left;

        // 左子数组的起始指针
        int l = left;
        // 右子数组的起始指针
        int r = mid + 1;

        while (l <= mid && r <= right) {
            // 当左子数组的当前元素小的时候，跳过，无逆序对
            if (array[l] <= array[r]) {
                // 放入临时数组
                arr[index] = array[l];
                // 临时数组下标+1
                index++;
                // 左子数组指针右移
                l++;
            } else { // 否则，此时存在逆序对
                // 放入临时数组
                arr[index] = array[r];
                // 逆序对的个数为 左子数组的终点-当前左子数组的当前指针
                count += mid - l + 1;
                // 临时数组+1
                index++;
                // 右子数组的指针右移
                r++;
            }
        }
        // 左子数组还有元素时，全部放入临时数组
        while (l <= mid) {
            arr[index++] = array[l++];
        }
        // 右子数组还有元素时，全部放入临时数组
        while (r <= right) {
            arr[index++] = array[r++];
        }
        // 将临时数组中的元素放入到原数组的指定位置
        for (int num : arr) {
            array[s++] = num;
        }
    }
}
